package com.datastructure.test.cutrope;

import java.util.ArrayList;
import java.util.Deque;

public class CutRope {

    public static void main(String[] args) {
        CutRope cutRope = new CutRope();
        int rope = cutRope.cutRope(8);
        System.out.println(rope);
    }

    public int cutRope (int n) {
        // write code here
        if(n==2){
            return 1;
        }
        ArrayList<Integer> data = new ArrayList<>();
        int sum = 0;
        int i = 2;
        while ((sum=sum +i)<n){
            data.add(i);
            i++;
        }
        int result = 1;
        sum=0;
        for (int j = 0; j < data.size(); j++) {
            sum+=data.get(j);
            result*=data.get(j);
        }
        result*=(n-(sum));
        return result;
    }

    private void dfs(int[] res, int start, int target, Deque<Integer> deque, ArrayList<ArrayList<Integer>> data) {
        if(target<0){
            return;
        }
        if(target==0&&deque.size()>0){
            data.add(new ArrayList<>(deque));
        }
        for (int i = start; i < res.length; i++) {
            deque.add(res[i]);
            dfs(res,i,target-res[i],deque,data);
            deque.removeLast();
        }
    }
}
